package elementaryAlgorithm;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 102. 二叉树的层序遍历
 * 给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
 *
 *
 *
 * 示例：
 * 二叉树：[3,9,20,null,null,15,7],
 *
 *     3
 *    / \
 *   9  20
 *     /  \
 *    15   7
 * 返回其层序遍历结果：
 *
 * [
 *   [3],
 *   [9,20],
 *   [15,7]
 * ]
 *
 * */
public class SequenceTraversalOfBinaryTree {

    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(15);
        TreeNode node2 = new TreeNode(7);
        TreeNode node3 = new TreeNode(20,node1,node2);
        TreeNode node4 = new TreeNode(9);
        TreeNode root = new TreeNode(3,node4,node3);
        SequenceTraversalOfBinaryTree sequenceTraversalOfBinaryTree = new SequenceTraversalOfBinaryTree();
        sequenceTraversalOfBinaryTree.levelOrder(root);
    }

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode node = root;
        queue.add(node);
        int length = 0;
        while(!queue.isEmpty()){
            length = queue.size();
            List<Integer> list = new ArrayList<>();
            while (length -- >0){
                node = queue.remove();
                list.add(node.val);
                System.out.println(node.val);
                if (node.left != null){
                    queue.add(node.left);
                }
                if (node.right != null){
                    queue.add(node.right);
                }
            }
            result.add(list);
        }
        return result;
    }
}
